A matrix power series is represented as:
            F      ⁡              (        A        )              =                  ∑                  i          =          1                n            ⁢              A        i              ,where A is a matrix with respective entries aij. In performing such a calculation, one may refer to
      S    i    =            ∑              j        =        1            i        ⁢          A      j      as the ith partial sum.
The calculation of such a power series for a matrix may arise in many contexts. For example, in graph theory, one may desire to analyze paths and their respective efficiencies (i.e., shortest, fastest, cheapest, etc.) through a graph connecting a set of nodes. A graph is a set of nodes and a set of paths interlinking some or all of the nodes. Graphs are used to solve many types of problems, such as finding the shortest, cheapest and/or fastest path between two places represented by nodes of a graph. Often graphs are used to give an answer to the question whether at least one path exists at all between two nodes.
For example, a complex networking topology comprising many different servers can be modelled by a graph. The graph can be used to find out whether there is at least one way for two specific servers to reach each other and connect to each other.
The following formalism can solve this type of problem. A graph G=(P, B) with nodes from a set P={p0, p1, p2, . . . , pn-1} and paths from a set B ⊂P×P may be represented by the following n×n matrix:
A(G)=(aij) where aij={1 if (pi, pj) ε B; 0 else} A(G) is called an adjacency matrix. In the case of a non-directed graph, each path between two nodes has an opposite path, so the adjacency matrix is symmetric.
From graph theory, it is known that when raising the adjacency matrix to power k an element akij of the resulting matrix (A(G))k corresponds to the number of paths with length k from node pi to node pj. The maximum path length in a graph consisting of n nodes is n. In longer paths, at least one node is visited two times.
A matrix W may be defined that indicates whether or not a path exists between two nodes pi, pj of a graph. The path matrix of a graph G is defined asW(G)=sig(A+A2+A3+ . . . +An)where sig is the sign function for a matrix M, defined as:sig(M)=sig(mij)={1 if mij≠0; 0 else}
Thus, calculation of the path matrix W requires computation of a matrix power series as defined above. A method is needed for calculating such a series.
A matrix power series may arise in many other areas of computation. For example, the familiar matrix exponential expression:
      ⅇ    A    =            ∑              n        =        0            ∞        ⁢                  A        n                    n        !            arises often in linear algebraic equations such as solutions to a coupled set of linear differential equations.
Known methods for calculating such a matrix polynomial typically involve an iterative process in which each matrix power in the series is computed and then stored. Upon the generation of all the terms of the series, the series is summed to provide the final result. For example, given the matrix A, first matrix A2 is calculated and stored, then matrix A3 is calculated and stored, and so on until matrix An is reached. Finally, all powers A1, . . . , An of matrix A are summed. From this sum, the path matrix is calculated in the last step.
The disadvantage of this approach is that memory consumption may be very large, since all intermediate results (the terms A1, . . . , An) must be kept in memory until the sum is calculated. For example, if n=1000, then each matrix A contains 10002=1 million entries. Since 1000 matrix powers have to be calculated, a total of 109 matrix elements must be kept in memory, or written temporarily on disk if the memory is not sufficient. If each of the matrix elements is a 4-byte integer value, then about 4 GB of memory or disk space is needed. Therefore, even for relatively small n, this simple method of calculating the path matrix is not very useful.
Thus a need exists for an efficient method for calculating a matrix power series.